package com.example.tree.segmenttree;

import java.util.ArrayList;
import java.util.List;

/**
 * 请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
 * 1. add(int num)
 * 将数字 num 添加到当前数字列表的最后面。
 * 2. getProduct(int k)
 * 返回当前数字列表中，最后 k 个数字的乘积。
 * <p>
 * 你可以假设当前列表中始终 至少 包含 k 个数字。
 * <p>
 * 题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
 * <p>
 * 示例：
 * 输入：
 * ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","g
 * etProduct","add","getProduct"]
 * [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
 * <p>
 * 输出：
 * [null,null,null,null,null,null,20,40,0,null,32]
 * <p>
 * 解释：
 * ProductOfNumbers productOfNumbers = new ProductOfNumbers();
 * productOfNumbers.add(3);        // [3]
 * productOfNumbers.add(0);        // [3,0]
 * productOfNumbers.add(2);        // [3,0,2]
 * productOfNumbers.add(5);        // [3,0,2,5]
 * productOfNumbers.add(4);        // [3,0,2,5,4]
 * productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
 * productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
 * productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
 * productOfNumbers.add(8);        // [3,0,2,5,4,8]
 * productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
 */
public class Leetcode1352_ProductOfNumbers {
    public static void main(String[] args) {
        ProductOfNumbers2 productOfNumbers = new ProductOfNumbers2();
        productOfNumbers.add(3);
        productOfNumbers.add(0);
        productOfNumbers.add(2);
        productOfNumbers.add(5);
        productOfNumbers.add(4);
//        System.out.println(productOfNumbers.getProduct(2));
//        System.out.println(productOfNumbers.getProduct(3));
        System.out.println(productOfNumbers.getProduct(3));
//        productOfNumbers.add(8);
//        System.out.println(productOfNumbers.getProduct(2));


    }

    /**
     * 解法二:前缀乘积
     * <p>
     * products[n-k, k] = pre[n] / pre[n-k] 其中pre[i]表示前i个元素的乘积(中间没有0的情况)
     */
    static class ProductOfNumbers2 {
        private List<Integer> pre;

        public ProductOfNumbers2() {
            pre = new ArrayList<>();
            pre.add(1);
        }

        public void add(int num) {
            if (num == 0) { // 遇到0需要将之前所有计算过的前缀积丢弃
                pre = new ArrayList<>();
                pre.add(1);
            } else {
                pre.add(pre.get(pre.size() - 1) * num);
            }

//            for (int i = 0; i < pre.size(); i++) {
//                System.out.println(i + ", " + pre.get(i));
//            }
//            System.out.println("======================");
        }

        public int getProduct(int k) {
//            System.out.println("getProduct size" + pre.size());
//            for (int i = 0; i < pre.size(); i++) {
//                System.out.println("getProduct i:" + i + ", " + pre.get(i));
//            }
            if (pre.size() <= k) { // 如果维护的前缀积列表长度小于K，说明在后K个中出现过的0，导致长度不够K，因此直接返回0即可
                return 0;
            }
            return pre.get(pre.size() - 1) / pre.get(pre.size() - 1 - k);
        }
    }

    /**
     * 暴力法
     */
    static class ProductOfNumbers {

        private List<Integer> numsList;

        public ProductOfNumbers() {
            numsList = new ArrayList<>();

        }

        public void add(int num) {
            numsList.add(num);

        }

        public int getProduct(int k) {
            int size = numsList.size();
            if (size < k) {
                return 0;
            }
            int res = 1;

            for (int i = size - k; i < size; i++) {
                res *= numsList.get(i);
            }

            return res;

        }
    }
}
